package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/'>验证二叉树的前序序列化(Verify Preorder Serialization of a Binary Tree)</a>
 * <p>序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。</p>
 * <p>
 * <pre>
 *          9
 *        /   \
 *       3     2
 *      / \     \
 *     4   1     6
 * </pre>
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 * </p>
 * <p>给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。</p>
 * <p>保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。</p>
 * <p>你可以认为输入格式总是有效的。例如它永远不会包含两个连续的逗号，比如 "1,,3" 。</p>
 * <p>注意：不允许重建树。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
 *      输出: true
 *
 * 示例 2:
 *      输入: preorder = "1,#"
 *      输出: false
 *
 * 示例 3:
 *      输入: preorder = "9,#,#,1"
 *      输出: false
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= preorder.length <= 10^4</li>
 *     <li>preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/4/8 10:58
 */
public class LC0331VerifyPreorderSerializationOfBinaryTree_M {

    static class Solution {

        /**
         * <b>树中所有节点的入度之和等于出度之和。</b>
         * <ul>
         *     <li>入度：有多少节点指向当前节点</li>
         *     <li>出度：当前节点指向多少个节点</li>
         * </ul>
         * <p>
         *     在一棵二叉树中：
         *     <ul>
         *         <li>每个空节点提供提供0个出度 和 1个入度</li>
         *         <li>每个非空节点会提供2个出度 和 1个入度(根节点的入度是0)</li>
         *     </ul>
         * </p>
         */
        public boolean isValidSerialization(String preorder) {
            int length = preorder.length();
            int currIndex = 0;
            int slots = 1;
            while (currIndex < length) {
                if (slots == 0) {
                    return false;
                }
                if (preorder.charAt(currIndex) == ',') {
                    ++currIndex;
                } else if (preorder.charAt(currIndex) == '#') {
                    // 入度为1，出度为0.总的-1
                    --slots;
                    ++currIndex;
                } else {
                    // 遇到数字字符，通过while循环找到完整的数字
                    while (currIndex < length && preorder.charAt(currIndex) != ',') {
                        ++currIndex;
                    }
                    // 入度为1，出度为2.总的+1
                    ++slots;
                }
            }
            return slots == 0;
            //
            //String[] values = preorder.split(",");
            //// 出度为+，入度为-
            //int diff = 1;
            //for (String value : values) {
            //    diff -= 1;
            //    if (diff < 0) {
            //        return false;
            //    }
            //    if (!value.equals("#")) {
            //        diff += 2;
            //    }
            //}
            //return diff == 0;
        }

        public boolean isValidSerialization2(String preorder) {
            String[] values = preorder.split(",");
            // 使用一个数组模拟栈
            String[] stack = new String[values.length];
            int curIndex = -1;
            for (String value : values) {
                stack[++curIndex] = value;
                while (curIndex >= 2 && stack[curIndex].equals("#") && stack[curIndex - 1].equals("#") && !stack[curIndex - 2].equals("#")) {
                    curIndex -= 3;
                    stack[++curIndex] = "#";
                }
            }
            return curIndex == 0 && stack[curIndex].equals("#");
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValidSerialization("#,#,3,5,#"));
    }
}
